package cn.edu.xjtu.carlWay.dpRepractice.perfectSquares;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * @author Hydrion-QLz
 * @date 2022-05-01 10:02
 * @description https://leetcode-cn.com/problems/perfect-squares/
 * <p>
 * 279. 完全平方数
 * 给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
 * <p>
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 */
class Solution {
    public int numSquares(int n) {
        ArrayList<Integer> arr = generateArr(n);
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 100000);
        dp[0] = 0;
        for (int num : arr) {
            for (int i = num; i < dp.length; i++) {
                dp[i] = Math.min(dp[i], dp[i - num] + 1);
            }
        }
        return dp[n];
    }

    private ArrayList<Integer> generateArr(int n) {
        ArrayList<Integer> arr = new ArrayList<>();
        int end = (int) Math.sqrt(n) + 1;
        for (int i = 1; i < end; i++) {
            arr.add((int) Math.pow(i, 2));
        }
        System.out.println(arr);
        return arr;
    }
}